package lc;

public class SearchInRotatedSortedArray {
    public int search(int[] A, int target) {
    	return searchR(A, 0, A.length-1, target);
    }

    int searchR(int [] A, int start, int end, int target) {
    	if (start > end) {
    		return -1;
    	}
    	else if (A[start] == target) {
    		return start;
    	}
    	else if (A[end] == target) {
    		return end;
    	}
    	
    	int mid = (start+end)/2;
    	if (A[mid] == target) {
    		return mid;
    	}
    	
    	if (A[mid] > A[start]) {
    		if (target > A[mid]) {
    			return searchR(A, mid+1, end, target);
    		}
    		else if (target > A[start]) {
    			return searchR(A, start, mid-1, target);
    		}
    		else {
    			return searchR(A, mid+1, end, target);    			
    		}
    	}
    	else {
    		if (target < A[mid]) {
    			return searchR(A, start, mid-1, target);    			
    		}
    		else if (target < A[end]) {
    			return searchR(A, mid+1, end, target);
    		}
    		else {
    			return searchR(A, start, mid-1, target);
    		}
    	}
    }

    public static void main(String ...strings) {
    	SearchInRotatedSortedArray sol = new SearchInRotatedSortedArray();
    	sol.search(new int [] {3,4,5,6,7,0,1,2}, 1);
    	sol.search(new int [] {1}, 2);
    }

}
